Lambda the Ultimate

Microsoft recently demoed a very interesting system for kids called Kodu. Kodu lets kids 'program' their own games for Xbox 360.

The language lets kids write programs like this:
when [game-pad] [left-click] do [fire] [at-monster]

Except game-pad, left-click, etc. are cartoonish icons kids pick out from context relevant lists.

This summary is based on watching two videos, at most a few minutes in length :) The video in the link is probably most relevant. There doesn't seem to be any more technical detail available on the web.

ompilers transform programs, either to optimize performance or to translate language-level constructs into hardware primitives. For concurrent programs, ensuring that a transformation preserves the semantics of the input program can be challenging. In particular, the emitted code must correctly emulate the semantics of the language-level memory model when running on hardware with a relaxed memory model. In this paper, we present a novel proof methodology for proving the soundness of compiler transformations for concurrent programs. Our methodology is based on a new formalization of memory models as dynamic rewrite rules on event streams. We implement our proof methodology in a first-of-its-kind semi-automated tool called Traver to verify or falsify compiler transformations. Using Traver, we prove or refute the soundness of several commonly used compiler transformations for various memory models. In this process, we find subtle bugs in the CLR JIT compiler and in the JSR-133 Java JIT compiler recommendations.

The goal is to reason about the effects that different memory models may have on the validity of transformations. Program execution is modeled as an event stream, with the memory model being able to alter the event stream by swapping or eliminating events. Each concurrent execution thread produces a separate event stream. The event stream produced by the execution of the concurrent program is the (possibly altered) result of merging the event streams of each component. The validity of transformation can thus be proved relative to a specific memory model (i.e., a set of stream rewrite rules).

Traver lives here.

The New York Time says Data Analysts Captivated by Power of R.

R is ... the name of a popular programming language used by a growing number of data analysts inside corporations and academia. It is becoming their lingua franca partly because data mining has entered a golden age, whether being used to set ad prices, find new drugs more quickly or fine-tune financial models. Companies as diverse as Google, Pfizer, Merck, Bank of America, the InterContinental Hotels Group and Shell use it.

Hmmm, "fine tune financial models". Does R stand for Recession?

More seriously, does data mining plus multi-core machines add up to an important language direction for the next few years? How well does R fare on such boxen?

More on R previously on LtU here and here.

With 2008 winding to a close, here's a question to you: what was noteworthy about 2008 as far as programming languages were concerned? To paraphrase Ehud, on topic are notable news about PLT research (direction, fads, major results) (2) notable news about programming languages (whether about specific languages, or about families etc.) and (3) notable news about industrial use of languages/language-inspired techniques (adoption, popularity).

While we're at it, let's score the predictions made at the beginning of the year and laugh at how young and naive we once were or at least make excuses about why our foretelling didn't quite pan out as predicted.

Functional Pearl: Type-safe pattern combinators, by Morten Rhiger:

Macros still have not made their way into typed higher-order programming languages such as Haskell and Standard ML. Therefore, to extend the expressiveness of Haskell or Standard ML gradually, one must express new linguistic features in terms of functions that fit within the static type systems of these languages. This is particularly challenging when introducing features that span across multiple types and that bind variables. We address this challenge by developing, in a step-by-step manner, mechanisms for encoding patterns and pattern matching in Haskell in a type-safe way.

This approach relies on continuation-passing style for a full encoding of pattern matching. Tullsen's First-Class Patterns relies on a monadic encoding of pattern matching to achieve abstraction over patterns. Given the relationship between CPS and monads, the two approaches likely share an underlying structure.

Abstracting over patterns yields a whole new level of abstraction, which could significantly improve code reuse. The only concern is compiling these more flexible structures to the same efficient pattern matching code we get when the language natively supports patterns. Section 4.9 discusses the efficiency concerns, and suggests that partial evaluation can completely eliminate the overhead.

Books on two of the languages that get a lot of airplay on LtU have made the finalist list for this year's Jolt awards.

Books Technical
* High Performance MySQL by Baron Schwartz, Peter Zaitsev, Vadim Tkachenko, Jeremy Zawodny, Arjen Lentz, Derek J. Balling (O'Reilly Media)
* Java Power Tools by John Ferguson Smart (O'Reilly Media)
* Programming in Scala by Martin Odersky, Lex Spoon, and Bill Venners (Artima Press)
* Real World Haskell by John Goerzen, Bryan O'Sullivan, Donald Bruce Stewart (O'Reilly Media)
* The iPhone Developer's Cookbook: Building Applications with the iPhone SDK by Erica Sadun (Addison-Wesley Professional)

Congratulations to Martin, Lex, Bill, John, Bryan, and Don!

Whether or not either book wins, it's quite a sea change that two sophisticated, statically typed functional programming languages with research origins are getting so much mainstream attention.

From the FAQ

How are the winners selected?

Our judges not only examine the standard criteria of audience suitability, productivity, innovation, quality, ROI, risk and flexibility, but also seek to honor products that are ahead of the curve. Jolt-winning products are universally useful; are simple, yet rich in functionality; redefine their product space; and/or solve a nagging problem that has consistently eluded other products and books.

With the recent popularity of the comparison between PLs and Religions (reddit, slashdot), I thought it'd be mildly amusing to see what other comparisons were out there on the intarweb.

Here's the list for the meme that I collected of If Programming Languages were ...

• Religions
• Cars
• Boats
• Women
• Girlfriends
• Subcultures
• Mixed Drinks
• Music
• Rock Bands
• Art
• Languages
• Christmas Songs
• Philosophers

Probably others that I missed. (Note: There's probably material in here to offend all). (Personally, I think the obvious missing comparison is If Programming Languages Were Tools. I nominate Assembler as the Stick, being the most primitive).

Programmable Concurrency in a Pure and Lazy Language, Peng Li's 2008 PhD dissertation, is a bit more implementation focused than is common on LtU. The paper does touch on a wide range of concurrency mechanisms so it might have value to any language designer considering ways to tackle the concurrency beast.

First, this dissertation presents a Haskell solution based on concurrency monads. Unlike most previous work in the field, this approach provides clean interfaces to both multithreaded programming and event-driven programming in the same application, but it also does not require native support of continuations from compilers or runtime systems. Then, this dissertation investigates for a generic solution to support lightweight concurrency in Haskell, compares several possible concurrency configurations and summarizes the lessons learned.

The paper's summary explains what I like most about it:

the project ... solves a systems problem using a language-based approach. Systems programmers, Haskell implementors and programming language designers may each find their own interests in this dissertation.

Even if concurrency isn't your thing, section 6.3 describes the author's findings on the pros and cons of both purity and laziness in a systems programming context.

A much beloved and widely used example showing the elegance and simplicity of lazy functional programming represents itself as "The Sieve of Eratosthenes." This paper shows that this example is not the sieve and presents an implementation that actually is.

Starting with the classic one-liner sieve (p : xs) = p : sieve [x | x <- xs, x ‘mod‘ p > 0] O'Neill proceeds to show why this standard rendition of the Sieve of Eratosthenes does not in fact "cross-off" the multiples of each prime in the same way the "real" Sieve does.

She notes that "Some readers may feel that despite all of these concerns, the earlier algorithm is somehow “morally” the Sieve of Eratosthenes. I would argue, however, that they are confusing a mathematical abstraction drawn from the Sieve of Eratosthenes with the actual algorithm. The algorithmic details, such as how you remove all the multiples of 17, matter."

A fun read.

On December 9, 1968, Dr. Douglas C. Engelbart and the Augmentation Research Center (ARC) at Stanford Research Institute staged a 90-minute public multimedia demonstration at the Fall Joint Computer Conference in San Francisco. It was the world debut of personal and interactive computing: for the first time, the public saw a computer mouse, which controlled a networked computer system to demonstrate hypertext linking, real-time text editing, multiple windows with flexible view control, cathode display tubes, and shared-screen teleconferencing.

To commemorate this famous event, commonly known as the mother of all demos, SRI held a 40th anniversary celebration at Stanford today. As a small tribute to the innovative ideas that made up the demo, it is befitting to mention some of the programming languages that were used by Engelbart's team. A few were mentioned in passing in the event today, making me realize that they are not that widely known.

The Tree Meta Language was used for describing translators, which were produced by the Tree Meta compiler-compiler. MOL940 ("Machine Oriented Language" for the SDS 940) was an Algol-like high level language for system programming which allowed the programmer to switch to machine-level coding where necessary. Alas (and ironically), I have not found the primary documents about these languages online. Section IV of Engelbart's Study for the development of Human Augmentation Techniques gives an account of the language and tools that were used in the project, and includes an example giving the metalanguage description for part of the Control Language. Figure 8 in in this document is a useful overview of the system and the compilers and compiler compilers used to build it. The tech report Development of a Multidisplay, Time-Shared Computer Facility and Computer-Augmented Management-System Research (only the abstract of which is online) also mentions "four Special-Purpose Languages (SPL's), for high-level specification of user control functions" which sound intriguing. The tech report specifying MOL 940 is also apparently not available online.

If I understood what Andries van Dam said, the Language for Systems Development (LSD) developed at Brown, which targeted OS/360 and was based on PL/I, was influenced by the work of Engelbart's team. They were also claiming to have built the first (or one of the first) cross-compiler.

When asked about prior work that influenced them, SNOBOL was mentioned as an important influence. The influence the demo had on programming languages was manifested by having Alan Kay's talk conclude the event (he did not mention Smalltalk once in his talk, by the way, but it was mentioned a couple of times earlier in the day).